# 题目：给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点，注意树中的节点除了有两个分别指向左子节点和右子节点的指针，
# 还有一个指向父节点的指针
import typing
from provate import TreeNode




# 如果一个节点有右子树，那么他的下一个节点就是它右子树的最左的子节点
# 如果一个节点A没有右子树，那么：
#     1、如果它是其父子节点的左子节点，那么他的下一个节点便是它的父节点
#     2、如果它是父节点的右子节点，那么就需要沿着父子节点的方向一直遍历，直到遍历到一个节点B是其父节点的左子节点,这时候A的下一个节点就是B的父节点
#     3、如果2中找不到，那么说明这个节点A是二叉树中最右边的节点

def getNext(pnode:TreeNode):
    if pnode is None:
        return None

    p_next = None

    if pnode.rightchild is not None:
        p_right = pnode.rightchild
        while p_right.leftchild is not None:
            p_right = p_right.leftchild
        p_next = p_right
    if pnode.parant is not None:
        p_current = pnode
        p_parant = pnode.parant

        while p_parant is not None and p_current == p_parant.rightchild:
            p_current = p_parant
            p_parant = p_parant.parant

        p_next = p_parant

    return  p_next


